package org.zjx.algorithm;


import org.zjx.core.RouteGraph;
import org.zjx.entity.Location;
import org.zjx.model.route.Route;

import java.util.*;

/**
 * A*寻路算法实现
 * 特点：结合Dijkstra的准确性和启发式搜索的高效性
 */
public class AStarPathFinding implements PathFindingStrategy {

    private static class NodeInfo {
        final Location previous;
        final Route route;
        final int gScore; // 实际耗时
        final int fScore; // 预估总耗时

        NodeInfo(Location previous, Route route, int gScore, int fScore) {
            this.previous = previous;
            this.route = route;
            this.gScore = gScore;
            this.fScore = fScore;
        }
    }

    @Override
    public List<Route> findPath(RouteGraph graph, Location start, Location end) {
        // 参数校验
        Objects.requireNonNull(graph, "路由图不能为null");
        Objects.requireNonNull(start, "起点不能为null");
        Objects.requireNonNull(end, "终点不能为null");

        // 初始化数据结构
        Map<Location, NodeInfo> nodeInfoMap = new HashMap<>();
        PriorityQueue<Location> openSet = new PriorityQueue<>(
                Comparator.comparingInt(loc -> nodeInfoMap.get(loc).fScore));

        // 设置起点
        int hScore = heuristic(start, end);
        nodeInfoMap.put(start, new NodeInfo(null, null, 0, hScore));
        openSet.add(start);

        while (!openSet.isEmpty()) {
            Location current = openSet.poll();

            // 到达终点
            if (current.equals(end)) {
                return buildPath(nodeInfoMap, end);
            }

            // 探索邻接节点
            for (Route route : graph.getRoutesFrom(current)) {
                Location neighbor = route.getEnd();
                int newGScore = nodeInfoMap.get(current).gScore + route.getTime();

                // 发现更优路径
                if (!nodeInfoMap.containsKey(neighbor) ||
                        newGScore < nodeInfoMap.get(neighbor).gScore) {

                    int newFScore = newGScore + heuristic(neighbor, end);
                    nodeInfoMap.put(neighbor,
                            new NodeInfo(current, route, newGScore, newFScore));
                    openSet.add(neighbor);
                }
            }
        }

        return null; // 不可达
    }

    /**
     * 启发式函数（预估剩余耗时）
     * @param a 当前位置
     * @param b 目标位置
     * @return 预估耗时（秒）
     */
    private int heuristic(Location a, Location b) {
        if (!a.sameScene(b)) {
            return 300; // 跨场景保守估计
        }
        // 同场景基于距离估算（0.2公里/秒）
        return (int)(a.distanceTo(b) / 200.0);
    }

    /**
     * 构建路径（从终点回溯）
     */
    private List<Route> buildPath(Map<Location, NodeInfo> nodeInfoMap, Location end) {
        LinkedList<Route> path = new LinkedList<>();
        Location current = end;

        while (nodeInfoMap.get(current).previous != null) {
            NodeInfo info = nodeInfoMap.get(current);
            path.addFirst(info.route);
            current = info.previous;
        }

        return path;
    }
}